Many data and speech communications systems use digital data for organization and transmission of information. Digital data is often sent in short frames, packets or bursts, and digital systems generally require error detection and error correction to ensure reliable communication. In order to achieve such high reliability over noisy communication channels and storage media, convolutional codes have been developed and applied to successfully transmit and store digital data. In certain applications, it is desirable to transmit short frames or packets of data. Unfortunately, it is difficult to obtain powerful correction on short data packets.
Convolutional codes are an efficient and powerful class of error-correcting codes based on a trellis structure. A convolutional encoder is a finite-state machine driven by the data stream to be encoded. An encoder outputs successive groups of A encoder output bits for each group of B input bits (defining a B-group) received for transmission. The trellis serves as a record of all such A-group bit streams that may be output from the encoder, where the branches in the trellis correspond to permissible encoder state transitions and one A-group corresponds to each trellis branch. The A-groups that label the branches are a function of the specific encoder circuit used in a particular application.
In order to decode convolutionally-encoded information, a maximum-likelihood decoder determines which path through the trellis corresponds to the sequence of bits that was most likely sent by the encoder. To make such a determination, a decoder observes a certain trellis depth (or span) forward of the particular branch currently being decoded; this span may be the width of an entire message trellis or a portion thereof and is an encoder parameter known as the code's forward decision depth. The probability of a decoding error for a given trellis stage directly depends on the depth of observation forward of that branch; the decoding error probability decreases inversely with a span forward increase, until the span equals the code's forward decision depth. At this point, increasing the decoder observation depth does not yield any significant decrease in the probability of a decoding error. A problem arises when the decoder nears the end of a received code word; as the code word end is approached, there are not enough trellis stages forward of the branch being decoded for the decoder to properly decode the remaining bits with a similar low probability of error as at the beginning of the code word. Consequently, the decoder observation depth becomes necessarily shorter and the probability of error is elevated when the transmitted data frame itself is short.
There are currently several established methods for dealing with a poorly decoded end-section, including the tail-bit-termination method and the tail-biting method. The tail-bit-termination method appends extra bits (possibly known) to the sequence of message bits to be encoded in order to return the encoder to a known state. The decoder can utilize knowledge of the known last trellis state to reduce the probability of decoding error in the last segment of bits in a message.
However, use of the tail-bit-termination method is often a problem in applications requiring short data frames or bursts, such as in cellular communications, because of the increased code bits necessary to transmit a given data frame. Another technique, called the tail-biting method, alleviates the problem of adding additional bits to the end of a message by having the encoder start in a circuit state equal to the one that the encoder will end in. This may be accomplished by inserting the final m*B data bits of the message to be encoded into the encoder shift register, where m is the memory of the encoder, to initialize its state at the beginning of encoding so that the resulting output codeword is no longer a block of bits but rather is a circle that "bites its tail". By exploiting this property, a tail-biting decoder decodes all data with the same low probability of error. Tail-biting convolutional codes are the most efficient known class of short codes but, historically, decoding complexity has prevented their application on a broad scale.
Current tail-biting convolutional decoders, inclusive of the decoder first identifying the unknown starting state prior to initiating decoding, require significant microprocessor calculations, require more memory than standard decoding, are of higher complexity, and mandate repeated trellis traversals to properly decode the transmitted data frame. Accordingly, an improved decoder for digital data signals encoded with a convolutional tail-biting code is desired.